package demo29;

import java.util.LinkedList;

public class Test {

    public static void main(String[] args) {

//        System.out.println(-2147483648 == Integer.MIN_VALUE);
//        System.out.println(divide(-2147483648,1));
//        System.out.println(-2147483648/2);

//        System.out.println(divide(2147483647,-1));

//        System.out.println(divide(2147483647,3));
//        System.out.println(divide(2147483647,2));

        System.out.println(-82778243<<3);
        System.out.println(-662225944<<3);

        System.out.println(divide(-1021989372,-82778243));


//        System.out.println(-1<<3);

//        System.out.println(-2147483647<<3);

        //如果被除数比除数多2位以上，那么考虑先让这个数进两位
//        divide(-2147483648,1);

    }

    //dividend：被除数   divisor：除数
    public static int divide(int dividend, int divisor) {
        //检查最特殊的情况，int最小/-1的情况，会导致正数int溢出
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }else if(dividend == 0){
            //再判断被除数为0的情况
            return 0;
        }
        int result = 0; //用来保存结果
        int sum = 0;    //用来保存累加的数字，比较它与被除数的大小关系
        int step = 1;   //用来保存每次的除数被翻了多少倍
        int size;       //用来保存被除数与除数的位数差距
        LinkedList<Integer> lists1 = new LinkedList<>();//用来保存每轮改造的除数
        LinkedList<Integer> lists2 = new LinkedList<>();//用来保存每轮改造的除数对应的倍率
        //先判断除数与被除数是否符号相同（除数不为0）
        if((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)){
            if(dividend > 0 && divisor > 0) {
                //都是正数，将两者都改成负数
                dividend = -dividend;
                divisor = -divisor;
            }

            //改造除数
            int divisor2 = divisor;//改造除数，帮助更快的运算
            size = (""+dividend).length() - (""+divisor).length();
            if(size > 0){
                for (int i = 0; i < size && (""+divisor2).length()<9; i++) {
                    //每轮对除数乘8
                    if(divisor2 << 3 >= 0 || divisor2 < Integer.MIN_VALUE - (divisor2<<3) || (divisor2<<3) < dividend){
                        //越界
                        /*
                            divisor << 3 >= 0表示除数不可以越界
                            divisor2 < Integer.MIN_VALUE - (divisor2<<3)表示改造的除数乘9后不可以越界
                            (divisor2<<3) < dividend表示改造的除数乘8后不能越界
                         */
                        continue;
                    }
                    divisor2 = divisor2<<3;//乘8
                    step = step<<3;//乘8
                    //将对应的改造后的除数以及倍率存入对应的数组中
                    lists1.addFirst(divisor2);
                    lists2.addFirst(step);
                }
            }
            //先用被改造过的除数进行运算
            //都是负数
            while(lists1.size() != 0){
                //获取数组中配对的改造后的被除数以及倍率
                divisor2 = lists1.getFirst();
                step = lists2.getFirst();
                while(dividend < sum){
                    if(sum < Integer.MIN_VALUE - divisor2){
                        //越界
                        break;
                    }else{
                        //累减，直到超出被除数（dividend）
                        sum = sum + divisor2;
                        result = result + step;
                    }
                }
                if(dividend > sum){
                    //如果sum的结果超出了范围，就将此次的除数操作回滚
                    sum = sum - divisor2;
                    result = result - step;
                }
                lists1.removeFirst();
                lists2.removeFirst();
            }

            //都是负数
            while(dividend < sum){
                if(sum < Integer.MIN_VALUE - divisor){
                    //越界
                    break;
                }else{
                    //累减，直到超出被除数（dividend）
                    sum = sum + divisor;
                    result++;
                }
            }
            /*
                1.如果因为越界或者正好sum == dividend的话
                2.如果前面改造除数的时候因为溢出越界而跳出循环
                代表result是正确的，没有多加1次
             */
            if(dividend == sum || (sum < Integer.MIN_VALUE - divisor && dividend < sum)){
                return  result;
            }
            return result-1;//两个数符号相同，结果为正数
        }else{
            //除数和被除数，一正一负
            if(dividend < 0){
                //除数为正数
                divisor = -divisor;
            }else{
                //被除数为正数
                dividend = - dividend;
            }

            //改造除数
            int divisor2 = divisor;//改造除数，帮助更快的运算
            size = (""+dividend).length() - (""+divisor).length();
            if(size > 0){
                for (int i = 0; i < size && (""+divisor2).length()<9; i++) {
                    //每轮对除数x10
                    if(divisor2 << 3 >= 0 || divisor2 < Integer.MIN_VALUE - (divisor2<<3)){
                        //越界
                        /*
                            divisor << 3 >= 0表示除数不可以越界
                            divisor2 < Integer.MIN_VALUE - (divisor2<<3)表示改造的除数乘9后不可以越界
                            (divisor2<<3) < dividend表示改造的除数乘8后不能越界
                         */
                        continue;
                    }
                    divisor2 = divisor2<<3;//乘8
                    step = step<<3;//乘8
                    //将对应的改造后的除数以及倍率存入对应的数组中
                    lists1.addFirst(divisor2);
                    lists2.addFirst(step);
                }
            }

            //先用被改造过的除数进行运算
            //都是负数
            while(lists1.size() != 0){
                //获取数组中配对的改造后的被除数以及倍率
                divisor2 = lists1.getFirst();
                step = lists2.getFirst();
                while(dividend < sum){
                    if(sum < Integer.MIN_VALUE - divisor2){
                        //越界
                        break;
                    }else{
                        //累减，直到超出被除数（dividend）
                        sum = sum + divisor2;
                        result = result + step;
                    }
                }
                if(dividend > sum){
                    //如果sum的结果超出了范围，就将此次的除数操作回滚
                    sum = sum - divisor2;
                    result = result - step;
                }
                lists1.removeFirst();
                lists2.removeFirst();
            }

            //都是负数
            while(dividend < sum){
                if(sum < Integer.MIN_VALUE - divisor){
                    //越界
                    break;
                }else{
                    //累减，直到超出被除数（dividend）
                    sum = sum + divisor;
                    result++;
                }
            }
            /*
                1.如果因为越界或者正好sum == dividend的话
                2.如果前面改造除数的时候因为溢出越界而跳出循环
                代表result是正确的，没有多加1次
             */
            if(dividend == sum || (sum < Integer.MIN_VALUE - divisor && dividend < sum)){
                return  -result;
            }
            return -result+1;//两个数符号不同，结果为负数
        }
    }

}
